#include <iostream>
#include <string>
#include <stack>
#include <set>

using namespace std;


bool separate(const string &str, int &beginIndex, int offset, stack<string> &wordStack, set<string> dictionary){
	if(str.length() == beginIndex)
		return true;
	int endIndex = beginIndex + offset;
	while(dictionary.end() == dictionary.find(str.substr(beginIndex, endIndex - beginIndex)) && endIndex < str.length()){
		endIndex ++;
	}
	if(dictionary.end() != dictionary.find(str.substr(beginIndex, endIndex - beginIndex))){
		wordStack.push(str.substr(beginIndex, endIndex - beginIndex));
		beginIndex = endIndex;
		offset = 1;
		return separate(str, beginIndex, offset, wordStack, dictionary);
	}
	else{
		offset = wordStack.top().length();
		beginIndex -= offset;
		wordStack.pop();
		return separate(str, beginIndex, offset + 1, wordStack, dictionary);
	}
	return false;
}


int sepmain(){
	set<string> dictionary;
	dictionary.insert("a");
	dictionary.insert("am");
	dictionary.insert("David");
	dictionary.insert("Ha");
	dictionary.insert("Hi");
	dictionary.insert("He");
	dictionary.insert("Hello");
	dictionary.insert("I");

	const string str("HelloIamDavidHa");
	stack<string> wordStack;
	int beginIndex = 0, offset = 1;

	bool b = separate(str, beginIndex, offset, wordStack, dictionary);

	return 0;
}